Many logic technologies contain a wide variety of circuits, such as AND, NAND, OR, NOR, XNOR, AND-OR, AND-NOR, OR-NAND gates, etc... It is desirable to remove circuits in order to reduce the size and increase the operating speed of the logic network. Specifically, inverters in the logic network add delay and therefore a reduction in the number of inverters in critical paths of the network will result in an increase in the operating speed of the network.
When the library of available circuits contains alternative circuits whose functions are identical except for the polarity of the input and/or output signals, it is also desirable to use the least cost circuit (e.g., the smallest) from among these alternatives.
Inverters can often be removed by "pushing" inverters into the inputs or outputs of gates, and applying transformations, such as AND to a NOR or NAND, as shown in FIG. 1. One previous method for removing inverters involved examining small sections of the logic to find locations where inverters might be "pushed" into other circuits. However, this method is deficient in that it is not capable of recognizing pairs of inverters which can be merged across long paths in the network.
Another method for reducing inverters involves making a single pass through the logic, and assigning polarities to signals during the pass. This method has not been effective since it cannot be applied to networks in which circuits have more than one fan-out.
U.S. Pat. No. 4,703,435 and "Logic Synthesis Through Local Transformations", IBM J. RES. DEVELOP, Vol. 25, No. 4, July, 1981 both by Darringer et al disclose a logic synthesizer method for synthesizing a logic network in order to minimize the number of circuit elements in the logic network. The synthesizer method includes inputting a description of the network, translating the inputted description into an initial implementation of AND/OR logic, simplifying the logic network at the AND/OR level, transforming the simplified AND/OR level into a NAND/NOR implementation, and applying simplifying transformations at the NAND/NOR level.
U.S. Pat. No. 4,916,627 to Hathaway discloses a system for reducing a logic network having several gate levels to a specified number of gate levels. The system includes levelizing the gates of the network in a forward and backward direction, specifying a scoring function, and selecting one of the gates in a determined worst path of the network in accordance with the scoring function.
The article entitled "Switching Network Logic Approach to Sequential MOS Circuit Design" by Wu et al, IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN, Vol. 8, No. 7, July, 1989, pp. 782-794, and U.S. Pat. No. 4,700,316 to Nair each discloses a synthesis method in which a logic network is re-expressed as a graph with edges.
The following are further examples of systems which attempt to reduce signal propagation time delay in logic networks.
U.S. Pat. No. 4,636,966 discloses a method of arranging logic circuit elements on a circuit board which provides an arrangement which optimize signal propagation delay time.
U.S. Pat. No. 4,566,064 discloses a logic network which employs PASS transistors as logic circuits in order to reduce signal propagation delay time relative to conventional logic circuits such as NAND, NOR and inverters.